\documentclass[UTF8]{ctexart}
\usepackage{xltxtra}
\usepackage{graphicx}
\usepackage{float}
\usepackage{subfigure}
%图片排版

\usepackage{listings,xcolor}

\usepackage[top=2cm, bottom=2cm, left=2cm, right=2cm]{geometry}  
%\usepackage{algorithm}  
%\usepackage{algorithmicx}  
%\usepackage{algpseudocode}  
\usepackage{amsmath}

\title{二叉搜索树排序的实现}
\author{陈乐瑶\\ 信息与计算科学\quad 3210103710}
\date{\today}
\begin{document}
\maketitle
\pagestyle{plain}
\lstset{numbers=left,
numberstyle=\tiny,
keywordstyle=\color{blue!70}, commentstyle=\color{red!50!green!50!blue!50},
frame=shadowbox,
rulesepcolor=\color{red!20!green!20!blue!20},
columns=flexible
}

\section{设计思路}
\subsection{头文件的设计}
使用课本BinarySearchTree.h以及dsexceptions.h头文件
\subsection{外部函数的设计}
\textbf{目的：}通过二叉树算法实现数组的排序
\subsubsection{打乱数组函数：Shuffle}
\begin{lstlisting}[language={[ANSI]C++}]
template <typename Comparable>
void Shuffle(std::vector<Comparable> &_arr)
{
  srand(time(NULL));//确保每次随机结果不同
  for(int i=_arr.size()-1;i>0;i--)
    {
      int index = rand()%(i+1);
      std::swap(_arr[index],_arr[i]);
    }
  //输出打乱后的数组
  for(typename vector<Comparable>::iterator it=_arr.begin();it!=_arr.end();it++)
    {
      std::cout<<*it<<'\n';
    }
  std::cout<<'\b'<<"Finished Shuffle."<<std::endl;
}
\end{lstlisting}
\textbf{注意：}第11-15行用于测试Shuffle函数的正确性，当数组较大时可删去。
\subsubsection{数组排序函数：BSTSorting}
\begin{lstlisting}[language={[ANSI]C++}]
template <typename Comparable>
void BSTSorting(std::vector<Comparable> &_arr, int _mode = 0)
{
  if(_mode == 1||_mode == 0)
  {
    double begin_time = clock();//开始计时
    BinarySearchTree<Comparable> T;

    //判断是否需要乱序
    if(_mode == 1)
      {
	Shuffle(_arr);
      }

    //将数组输入BST
    for(typename vector<Comparable>::iterator it = _arr.begin();it != _arr.end();it++)
    {
      T.insert(*it);
    }

    double end_time = clock();//结束计时
    std::cout<<"Time Cost:"<<(double)(end_time-begin_time)/CLOCKS_PER_SEC<<std::endl;
    //统计运行时间  
    //通过BST将数组由小到大顺序输出
    T.printTree();
    std::cout<<"Finished Sorting."<<std::endl;
  }
  else//输入不正确的异常处理
    {
      #ifdef COMMAND
      #warning WRONG INPUT!
      #endif
      return;
    }
};
\end{lstlisting}
\textbf{注意：}

第6,21-22行用于测试算法效率，测试函数运行时可以删去。

第24-27行用于测试BSTSorting函数的正确性，当数组较大时可以删去。

\section{测试说明}
由于各种测试的方法类似，故自定义函数double\_test减少复制：
\begin{lstlisting}[language={[ANSI]C++}]
void double_test(double &N, int _mode)
{
  vector<double> _arr;
  for(double i = 0; i<N; i++)
    _arr.push_back(i);
  BSTSorting(_arr,_mode);
};
\end{lstlisting}

\subsection{函数运行测试}
以0～9的数组为例，通过三个test分别测试不同\_mode的结果，从而测试两个外部函数的正确性。
\begin{lstlisting}[language={[ANSI]C++}]
int main(int argc, char* argv[])
{
  double N = 10;
  //测试_mode==0的结果
  std::cout<<"test1:"<<std::endl;
  double_test(N,0);
  //测试_mode==1的结果
  std::cout<<"test2:"<<std::endl;
  double_test(N,1);
  //测试_mode!=0&&_mode!=1的结果
  std::cout<<"test3:"<<std::endl;
  vector<int> arr;
  BSTSorting(arr,2);
  return 0;
}
\end{lstlisting}

\textbf{输出结果：}
\begin{figure}[htbp]
  \includegraphics[width=0.13\textwidth]{fig11.png}
  \includegraphics[width=0.13\textwidth]{fig12.png}
  \includegraphics[width=0.13\textwidth]{fig13.png}
  \caption{函数运行测试结果}
\end{figure}

\subsection{函数效率测试}
通过调用time.h库中的clock()函数，利用运行时间反映效率。
\subsubsection{\_mode==0的最坏效率}
数组正序或逆序时效率最低，为$O(n^2)$。

\begin{lstlisting}[language={[ANSI]C++}]
int main(int argc, char* argv[])
{
  double N;
  std::cin>>N;
  double_test(N,0);
  return 0;
}
\end{lstlisting}

我们分别以N=10000和N=100000为例可以得到如下输出结果：
\begin{figure}[htbp]
  \includegraphics[width=0.2\textwidth]{fig21.png}
  \includegraphics[width=0.2\textwidth]{fig22.png}
  \caption{\_mode==0的最坏效率}
\end{figure}

经过多组数据测试绘制Time Cost——N图像并得到拟合曲线，根据拟合曲线对Time Cost和N分别取2的对数，从而得到一条直线，图像如下所示：
\begin{figure}[htbp]
  \centering
  \includegraphics[width=0.45\textwidth]{fig3.png}
  \includegraphics[width=0.45\textwidth]{fig4.png}
  \caption{\_mode==0的最坏效率图像}
\end{figure}

因此我们得到：\_mode==0的最坏效率为$O(n^2)$。

\subsubsection{\_mode==1的平均效率}
数组乱序函数使用的算法效率为O(n)，而BST排序算法平均效率为O(logn)，因此理论上该算法平均效率为O(nlogn)。
\begin{lstlisting}[language={[ANSI]C++}]
int main(int argc, char* argv[])
{
  double N;
  std::cin>>N;
  const int TIMES = 50;//重复测试次数
  for(int j=0; j<TIMES; j++)
  {
    double_test(N,1);
  }
  return 0;
}
\end{lstlisting}
同理，经过多组数据测试绘制Time Cost—N图像并得到拟合曲线，根据拟合曲线以及理论推算，绘制Time Cost—N*lnN，从而得到一条直线，图像如下所示：
\begin{figure}[htbp]
  \centering
  \includegraphics[width=0.45\textwidth]{fig5.png}
  \includegraphics[width=0.45\textwidth]{fig6.png}
  \caption{\_mode==1的平均效率图像}
\end{figure}

因此我们得到：\_mode==1的平均效率为$O(nlogn)$。

\subsection{内存泄漏测试}
\textbf{输入：}valgrind ./test

\textbf{输出：}
\begin{figure}[htbp]
  \centering
  \includegraphics[width=0.6\textwidth]{fig7.png}
  \caption{内存泄漏检查}
\end{figure}

\end{document}
